package com.liuwei.spring.cloud.junit.leetcode.interview;

import com.liuwei.spring.cloud.common.utils.Jackson;
import org.apache.commons.collections4.CollectionUtils;
import org.apache.commons.lang3.StringUtils;

import java.util.*;

public class PrefixTrie {

    /**
     * https://leetcode.cn/problems/implement-trie-prefix-tree/description/
     * @param args
     */
    public static void main(String[] args) {
        String[] ops = new String[]{"Trie","insert","search","search","startsWith","insert","search"};
        String[][] values = new String[][]{new String[]{},new String[]{"apple"}, new String[]{"apple"},new String[]{"app"},new String[]{"app"},new String[]{"app"},new String[]{"app"}};
        PrefixTrie solution = new PrefixTrie();
        List<String> result = solution.ops(ops,values);
        System.out.println(Jackson.toJSONString(result));
    }

    public List<String> ops(String[] ops,String[][] values){
        List<String> output = new ArrayList<>();
        Trie trie = null;
        for (int i = 0; i < ops.length; i++) {
            if(StringUtils.equalsIgnoreCase(ops[i],"Trie")){
                trie = new Trie();
                output.add(null);
            }
            if(StringUtils.equalsIgnoreCase(ops[i],"insert")){
                trie.insert(values[i][0]);
                output.add(null);
            }
            if(StringUtils.equalsIgnoreCase(ops[i],"search")){
                boolean result = trie.search(values[i][0]);
                output.add(String.valueOf(result));
            }
            if(StringUtils.equalsIgnoreCase(ops[i],"startsWith")){
                boolean result = trie.startsWith(values[i][0]);
                output.add(String.valueOf(result));
            }
        }
        return output;
    }

    class Trie {
        Map<String, Set<String>> dictionary = new HashMap<>();
        public Trie() {

        }

        public void insert(String word) {
            char[] chars = word.toCharArray();
            String key = "";
            for (int i = 0; i < chars.length; i++) {
                char index = chars[i];
                key = key + index;
                addDict(key,word);
            }
        }

        public boolean search(String word) {
            Set<String> set = dictionary.get(word);
            if(CollectionUtils.isNotEmpty(set)){
                return set.contains(word);
            }
            return false;
        }

        public boolean startsWith(String prefix) {
            return CollectionUtils.isNotEmpty(dictionary.get(prefix));
        }

        private void addDict(String key,String value){
            if(CollectionUtils.isEmpty(dictionary.get(key))){
                dictionary.put(key,new HashSet<>());
            }
            dictionary.get(key).add(value);
        }

        public boolean isEmpty(final Collection<?> coll) {
            return coll == null || coll.isEmpty();
        }

        public boolean isNotEmpty(final Collection<?> coll) {
            return !isEmpty(coll);
        }
    }
}
